1. Field of the Invention
This invention relates to computer networks and, more specifically, to the making of forwarding decisions for network messages.
2. Background Information
Computer networks typically comprise a plurality of interconnected entities. An entity may consist of any device, such as a computer or end station, that “sources” (i.e., transmits) or “sinks” (i.e., receives) datagrams (e.g., packets and/or frames). A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack). In many instances, several LANs may be interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (“WAN”) or internet that may span an entire country or continent.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a “bridging” function between two or more LANs. Alternatively, a switch may be utilized to provide a “switching” or interconnection function for transferring information between a plurality of LANs or end stations. Bridges and switches may operate at various levels of the communication protocol stack. For example, a switch may operate at layer 2 which, in the Open Systems Interconnection (OSI) Reference Model, is called the data link layer and includes the Logical Link Control (LLC) and Media Access Control (MAC) sub-layers. Data frames at the data link layer typically include a header containing the MAC address of the entity sourcing the message, referred to as the source address, and the MAC address of the entity to whom the message is being sent, referred to as the destination address. To perform the switching function, layer 2 switches examine the MAC destination address of each data frame received on a source port. The frame is then switched onto the destination port(s) associated with that MAC destination address. Ports used to couple switches to each other are generally referred to as a “trunk” ports, whereas ports used to couple switches to LANs or end stations are generally referred to as “access” ports.
Other network devices, commonly referred to as routers, may operate at higher communication layers, such as layers 3, 4 or even higher. Layers 3 and 4 of Transmission Control Protocol/Internet Protocol (TCP/IP) networks correspond to the IP and TCP/User Datagram Protocol (UDP) layers, respectively. Data packets or frames at the IP layer also include a header that contains an IP source address and an IP destination address. Routers or layer 3 switches may re-assemble or convert received data frames from one LAN standard (e.g., Ethernet) to another (e.g. token ring). Thus, layer 3 devices are often used to interconnect dissimilar subnetworks. Many equipment manufacturers include both layer 2 switching and layer 3 routing functions in a single device.
Virtual Local Area Networks
A computer network may also be segregated into a series of logical network segments. U.S. Pat. No. 5,394,402, issued Feb. 28, 1995 (the “'402 patent”), for example, discloses an arrangement for associating any port of a switch with any particular segregated network group. Specifically, according to the '402 patent, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. These VLAN designations are also associated with the messages that are received on these ports. In particular, every time a message is received on a given access port, the VLAN designation for that port, as stored in a memory portion of the bridge, is associated with the message. For convenience, each VLAN designation is often associated with a different color, such as red, blue, green, etc.
In many cases, it may be desirable to interconnect a plurality of these switches in order to extend the VLAN associations of ports in the network. By extending VLAN associations across multiple devices, those entities having the same VLAN designation function as if they are all part of the same LAN segment. Message exchanges between parts of the network having different VLAN designations are specifically prevented in order to preserve the boundaries of each VLAN segment or domain. In addition to the '402 patent, the Institute of Electrical and Electronics Engineers (IEEE) has promulgated the IEEE 802.1Q specification standard for Virtual Bridged Local Area Networks. The IEEE's 802.1Q standard supports VLANs and defines a specific VLAN-tagged message format for transmission on trunks.
IPv6
Although it has performed well, several deficiencies have been identified with the current version (four) of the Internet Protocol (IPv4). One of the primary deficiencies is the limited number of available addresses. Specifically, IPv4 provides for 32-bit addresses. IPv4 addresses are expected to be exhausted in the next few years. As a result, work has been ongoing to develop a replacement to IPv4. This replacement or next generation is known as Internet Protocol version 6 or IPv6.
FIG. 1 is a highly schematic block diagram of an IPv6 packet 100 which includes a plurality of fields. In particular, the IPv6 packet 100 includes a version field 102, a traffic class field 104, a flow label field 106, a payload length field 108, a next header field 110, and a hop limit field 112. The IPv6 packet 100 further includes a source address (SA) field 114, a destination address (DA) field 116 and a variable length data field 118. The SA and DA fields 114, 116 are each 128-bits in length. That is, while IPv4 defined 32-bit address spaces, IPv6 has 128-bit address spaces, substantially increasing the number of available IP addresses.
Several address types or formats have been defined for IPv6. Request for Comments (RFC) 2374, for example, defines so-called Aggregatable Global Unicast Addresses. The DA field 116 of FIG. 1 illustrates an Aggregatable Global Unicast Address, which includes a 3-bit format prefix (HP) field 120, which is set to binary “001”, a 13-bit Top-Level Aggregation (TLA) Identifier (ID) field 122, an 8-bit reserved field 124 to accommodate the growth in TLA IDs, a 24-bit Next-Level Aggregation (NLA) ID field 126, a 16-bit Site-Level Aggregation (SLA) ID field 128, which is similar to a subnet ID in IPv4, and a 64-bit interface ID field 130.
IPv6 also defines two types of local use or scoped unicast addresses: link-local unicast addresses and site-local unicast addresses. In contrast to the Aggregatable Global Unicast Addresses described above, link-local and site-local addresses are not globally unique. Instead, link-local addresses are unique only on a single link, while site-local addresses are unique only within a given site. Link-local addresses were developed to support auto-configuration, while site-local addresses were developed, at least in part, to allow computer networks that are not connected to the global Internet to nonetheless use IPv6 address schemes. A site, which is not rigorously defined in IPv6, is typically intended to cover a region of topology that belongs to a single organization and that is located within a particular geographic location. A link typically refers to a LAN or a bridged network.
FIG. 2 is a highly schematic block diagram of an IPv6 link-local unicast address 200. The link-local unicast address 200 includes a 10-bit prefix 202, which is set to binary “1111 1110 10”, to identify the address as a link-local unicast address. The prefix 202 is located at higher order bit positions 118 to 127, which may be represented by the notation <127:118>. Address 200 further includes a 54-bit intermediary field 204, which is set to null, i.e., all zeros, and a 64-bit interface ID field 206, which is similar to field 130 (FIG. 1), and is at bit positions <63:0>.
FIG. 3 is a highly schematic block diagram of an IPv6 site-local unicast address 300. The site-local unicast address 300 similarly includes a 10-bit prefix 302, which, in the context of a site-local unicast address, is set to binary “1111 1110 11”. The site-local unicast address 300 further includes a 38-bit intermediary field 304 which is also set to null, a 16-bit Site-Level Aggregation (SLA) Identifier (ID) field 306, which is similar to field 128 (FIG. 1) and a 64-bit interface ID field 308, which is similar to field 130 (FIG. 1), and is also at bit positions <63:0>.
Intermediate devices, such as routers, must only forward packets containing site-local addresses on outbound interfaces that are associated with the same site as the interface on which the packet was received. This is due, at least in part, to the fact that entities located within different sites may nonetheless be using the same interface ID values. Packets carrying link-local destination addresses are not meant to be forwarded by layer 3 (L3) devices at all, other than back out the logical interface on which they were received.
In addition to unicast addresses, IPv6 also provides for multicast destination addresses. According to RFC 2373, multicast addresses are only to be used as destination addresses and not as source addresses. FIG. 4 is a highly schematic illustration of a multicast destination address 400. Multicast address 400 includes an 8-bit prefix 402, which is set to binary “1111 1111” to identify the address as a multicast address. The multicast address 400 further includes a 4-bit flags field 404, which is defined as a set of four 1-bit flags. To date, only the last flag of the flags field 404 has a defined meaning, indicating whether the multicast address corresponds to a “well-known” multicast address, as assigned by the global internet numbering authority, or to a “transient” multicast address. The other flags are currently reserved. A 4-bit scope field 406 indicates whether the multicast message has a global scope or some limited scope. That is, IPv6 also defines multicast destination addresses that are unique only in some specified region of the network topology, called a zone. A group identifier (ID) field 408 specifies the address's multicast group. Nodes or entities can subscribe to receive messages addressed to a particular group ID in a specific zone.
Unlike unicast addresses, which can have at most three scopes, namely, link, site or global, multicast addresses can have up to sixteen different scopes, as permitted by the 4-bit scope field. More specifically, RFC 2373, “IP Version 6 Addressing Architecture”, dated July 1998 defines the following scopes for multicast addresses:
ValueScope0reserved1node-local2link-local3unassigned4unassigned5site-local6unassigned7unassigned8organization-local9unassignedAunassignedBunassignedCunassignedDunassignedEglobal scopeFreserved
As shown, a multicast destination address can have one of fourteen different scopes, putting aside the two reserved values (0 and F).
The definition of multiple scopes for both unicast and multicast addresses imposes complexities on intermediate network devices, such as routers, which need to process and forward packets from their interfaces at high rates of speed. More specifically, as is the case with scoped unicast addresses, scoped multicast addresses are not to be forwarded beyond the limits of the zone having the scope specified by the value of the scope field 406. This is due to the fact that entities within different zones of the same scope may be using the same multicast address values for different multicast groups. This can impose significant complexities for all but node-local and global multicast addresses. From a forwarding point of view, the node-local scope does not require very complicated processing because such addresses are not meant to be sent from a node's interface. If a router receives an IPv6 packet with a node-local destination address, it simply drops the packet as the packet can only have been received in error. For global scope destination addresses, no particular processing or handling is required because such addresses are guaranteed to be unique globally. The remaining twelve kinds of scoped multicast addresses, however, can impose complex processing requirements.
In the Internet Draft document entitled IPv6 Scoped Address Architecture, dated November 2001, the authors proposes the creation of a plurality of routing tables to forward site-local addresses. In particular, an intermediate network device whose interfaces are coupled to n different sites establishes n+1 routing tables; one for global addresses and one for each of the n sites. To forward a packet containing a site-local destination address, the router accesses the routing table associated with the site on which the packet was received and, if there is a match, forwards the packet on the identified outbound interface. This approach, however, as recognized in the Internet Draft document itself, increases protocol processing time, thereby reducing the efficiency of the intermediate device. Furthermore, for multicast addresses, it would require the creation and maintenance of numerous multicast routing tables, one for each zone of a certain multicast scope to which the intermediate network device is connected. As there are twelve possible non-global multicast scopes, each potentially requiring several tables, the introduction of scoped multicast addresses substantially increases the complexity of packet processing and forwarding, leading to a likely reduction in throughput.
Accordingly, a need exists for a system capable of forwarding scoped addresses, especially multicast addresses, efficiently.